前 n 个数字二进制中 1 的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

思想：

对于 x 来说，如果 x 二进制末尾是 1，那么它的二进制表示中 1 的个数显然就比其它二进制位与 x 相同，但是末尾是 0 的数多一个，我们用 1 与 x 进行异或即可得到这个数。当然，这个数就是 x - 1。所以当 x 是奇数时，我们只要知道了 x - 1 有多少个 1 就知道了 x 有多少个 1。

同理，当 x 二进制末尾是 0 时，那么它的二进制表示中 1 的个数与抹去末尾这个 0 后的个数是一样的，这个数就是 floor(x / 2)，也就是说知道了 floor(x / 2) 中 1 的个数，就知道了 x 有多少个 1。

作者：cml-r 链接：https://leetcode-cn.com/problems/w3tCBm/solution/jian-zhi-offer-ii-003-qian-n-ge-shu-zi-e-vmwu/

我的理解：

当x为奇数时，只需要知道 x-1 有多少个1 就知道 x 有多少个1；

当x为偶数时，它的二进制表示中 ,1 的个数与抹去末尾 0 的个数是一样的，所以这里使用 >> 进位符，每遍历一次都会向前进位；

什么是>>移位运算符呢？http://c.biancheng.net/view/5471.html

var countBits = function(n) {
    const binary = new Array(n);
    // 初始化数组
    binary[0] = 0;
    // 从1开始遍历数组
    for(let i = 0; i <= n; i++){
        // 如果是偶数，1的个数和它除以2后 1的个数是一样的，i二进制右移1位
        // 如果是奇数，等于上一个数+1  binary[i-1]+1
        binary[i] = i%2 ? binary[i-1]+1 : binary[i>>1];
    }
    return binary;
};